package tree;

import java.util.Arrays;

/**
 * @author : Rookie
 * @description : 最大二叉树
 * 二叉树的根是数组中的最大元素。
 * 左子树是通过数组中最大值左边部分构造出的最大二叉树。
 * 右子树是通过数组中最大值右边部分构造出的最大二叉树*
 * @date : 2023/10/25
 */
public class MaxBinaryTree {

    public static void main(String[] args) {
        int[] input = new int[] {3,2,1,6,0,5};
        TreeNode root = buildMaxTree(input);
        BinaryTreeUtil.Traversal.sequenceTraversal(root);
    }

    private static TreeNode buildMaxTree(int[] arr) {
        if (arr.length == 0) {
            return null;
        }
        int maxValIndex = getMaxValIndex(arr);
        System.out.println("最大值索引是：" + maxValIndex);
        TreeNode root = new TreeNode(arr[maxValIndex]);
        // 拆分数组
        int[] subLArr = new int[maxValIndex];
        int[] subRArr = new int[arr.length-maxValIndex-1];

        int rightIndex=0;
        for (int i = 0; i < arr.length; i++) {
            if (i < maxValIndex) {
                subLArr[i] = arr[i];
            }
            if (i > maxValIndex) {
                subRArr[rightIndex++] = arr[i];
            }
        }
        System.out.println("左侧数组是：" + Arrays.toString(subLArr));
        System.out.println("右侧数组是：" + Arrays.toString(subRArr));

        root.left = buildMaxTree(subLArr);
        root.right = buildMaxTree(subRArr);
        return root;
    }

    private static int getMaxValIndex(int[] arr) {
        int maxIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > arr[maxIndex]) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}
